package LeetCode.题库.中等;

/**
 * @author 挚爱之夕
 * @version 1.0
 * @implSpec 假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？
 * 输入: [7,1,5,3,6,4]
 * 输出: 5
 * @since 2022 - 10 - 22 - 22:21
 */
public class _63股票的最大利润 {
    public static void main(String[] args) {
        int[] prices = {7, 1, 5, 3, 6, 4};
        System.out.println(new Solution63().maxProfit1(prices));
    }
}
class Solution63{
    //暴力O(n2)
    public int maxProfit(int[] prices) {
        int res = 0;
        for(int i = 0; i < prices.length; i++){
            for(int j = i + 1; j < prices.length; j++){
                res = Math.max(res, prices[j] - prices[i]);
            }
        }
        return res;
    }
    //遍历一次O(n)
    public int maxProfit1(int[] prices) {
        int res = 0;
        int min = Integer.MAX_VALUE;
        for (int price : prices) {
            if (price < min) {
                min = price;
            } else if (price > min) {
                res = Math.max(res, price - min);
            }
        }
        return res;
    }
}
